相关链接
题目传送门:https://ly.men.ci/problem/196
题目大意
搞一个数据结构来维护一个长度为$n(n \le 10^5)$的序列。
并进行$m(m \le 10^5)$个操作,操作分为以下四种:
- 区间加$c(-10^4 \le c \le 10^4)$
- 区间除$d$。即对于单个元素$a_i$,除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
- 询问区间和
- 询问区间最值
解题报告
考虑将所有的相邻的并且值相同的位置合成一个块
考虑一次修改操作最多增加两个块,于是总的块数不会超过$n+m$
那么对于操作二,我们暴力应用到区间的每一个块上
因为每一个块最多进行$\log val$次的操作二就会消失
所以总的操作次数不会超过$O ((n+m) \log (10^4))$
现在考虑具体实现
不嫌麻烦的话,我们可以使用$Splay$。脑袋里想想还是很好写的
要好写一点的话,我们就用线段树,记录一下一个点的子树中所有的值是否相等
相关拓展
这种将相同值合并到一起来保证复杂度的题目还在雅礼集训的时候见过一次啊
当时是要求将编号$l \to r$的结点的父亲全部设为$x$,然后单点修改权值,查询某个点的子树和
也是将$fa$相同的点搞在一起,然后用$Splay$维护一下
Thank you for your article.Really looking forward to read more. Cool.
I read this paragraph fully about the resemblance of most up-to-date and previous technologies, it’s
remarkable article.
I’m gone to convey my little brother, that he should also go to see this webpage on regular basis to obtain updated from latest
gossip.
My brother suggested I might like this web site.
He was once totally right. This put up actually made my day.
You cann’t imagine simply how so much time I had spent for this information!
Thanks!
Excellent items from you, man. I’ve have in mind your stuff prior to and you are simply too fantastic.
I actually like what you have bought here, certainly like
what you are saying and the way in which you assert it. You’re making it enjoyable and you still take care of to
stay it sensible. I can’t wait to learn much more from
you. That is actually a tremendous site.
This blog was… how do I say it? Relevant!! Finally I have found something which helped me.
Appreciate it!
Thankfulness to my father who stated to me regarding this blog,
this weblog is in fact remarkable.
Excellent post however I was wanting to know if you could write a litte more on this topic?
I’d be very thankful if you could elaborate a little
bit more. Kudos!
I quite like reading through a post that can make men and women think.
Also, thanks for allowing for me to comment!
What’s up, just wanted to mention, I enjoyed this post.
It was funny. Keep on posting!
My partner and I stumbled over here from a different web page and thought I might as well check things out.
I like what I see so now i’m following you. Look forward
to finding out about your web page yet again.
We stumbled over here coming from a different website and thought I should check things out.
I like what I see so now i am following you. Look forward to looking into your web page repeatedly.
Hi there mates, its impressive piece of writing on the topic of educationand completely defined, keep it up all
the time.
I have read so many content concerning the blogger lovers but this piece of writing is
in fact a fastidious article, keep it up.
I’d have to examine with you here. Which is not one thing I usually do! I take pleasure in reading a post that may make folks think. Additionally, thanks for permitting me to comment!
Do you have a spam problem on this website; I also am a blogger, and I was wanting
to know your situation; many of us have created some
nice procedures and we are looking to trade methods with others, why not shoot me an e-mail if interested.
I will right away seize your rss as I can’t in finding your e-mail
subscription link or e-newsletter service. Do you have any?
Kindly let me recognise so that I may just subscribe.
Thanks.
Pretty! This has been an extremely wonderful post. Many thanks for providing this information.
Terrific post but I was wondering if you could write a litte more on this topic?
I’d be very grateful if you could elaborate a little bit
more. Thank you!
This is a topic that’s close to my heart… Best wishes! Exactly where are your contact details though?
I do believe all of the ideas you’ve offered in your post. They are very convincing and can definitely work. Still, the posts are very short for novices. Could you please prolong them a little from next time? Thank you for the post.
I’ve been surfing online greater than three hours nowadays, but I never found any attention-grabbing article like yours.
It is pretty price enough for me. Personally, if all
website owners and bloggers made good content material as you did, the net will likely be
a lot more useful than ever before.